package course.p3_arraysSort.exa06_countSort;

import org.junit.Test;

import java.util.Arrays;

public class CountSort {

    /**
     * 计数排序，此排序是很明显的空间换时间的做法
     * @param a 排序数组
     * @param b 输出数组
     * @param n 数组取值范围的最大值
     */
    public static void CountingSort(int[] a,int[] b,int n) {
        int k = n+1;
        int[] c = new int [k];
        int j,i;
        for(j=0;j<a.length;j++)
            c[a[j]] = c[a[j]] + 1;

        for (i=1; i < k; i++)
            c[i] = c[i] + c[i-1];

        for (j = 0; j < a.length; j++) {
            //注意这里的b数组里面一定要-1
            b[c[a[j]]-1] = a[j];
            c[a[j]] = c[a[j]] - 1;
        }
    }

    @Test
    public void countingSortTest() {
        int[] numbs = {2,5,3,0,2,3,0,3};
        int[] result = new int[numbs.length];
        CountingSort(numbs,result,5);
        System.out.println(Arrays.toString(result));
    }


}
